package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * 6100. 统计放置房子的方式数
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/26 18:15
 */
public class CountHousePlacements {


    public int countHousePlacements(int n) {
        long i = find(n);
        return (int) (i * i % 1000000007);
    }

    private long find(int n) {
        if (n == 1) {
            return 2;
        }
        if (n == 2) {
            return 3;
        }
        int a = 2;
        int b = 3;
        int c = 0;
        for (int i = 2; i < n; i++) {
            c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return b;
    }

}
